import java.util.Arrays;
import java.util.HashSet;
import java.util.Stack;

public class Main{
    public int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> hashMap = new HashSet<>();
        int cnt = 0;

        for(int i = 0;i < stones.length();i++){
            hashMap.add(jewels.charAt(i));
        }

        for(int j = 0;j < stones.length();j++){
            if(hashMap.contains(stones.charAt(j))){
                cnt++;
            }
        }
        return cnt;
    }

    //插入排序：选择合适的位置插入
    public static void insertSort(int[] arr){
        if(arr == null) return;
        for (int i = 1;i < arr.length;i++){
            //j 下标前的元素比较
            int j = i - 1;
            int tem = arr[i];
            for (; j >= 0 ; j--) {
                if(arr[j] > tem){
                    arr[j + 1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+ 1] = tem;
        }
    }

    //希尔排序:增量减小的插入排序
    //法一
    public static void shellSort(int[] arr){
        if(arr == null) return;
        if(arr.length == 1) return;

        int gap = arr.length;
        while(gap > 0){
            gap = gap / 2;
            insertSort1(arr,gap);
        }
    }
    public static void insertSort1(int[] arr,int gap){

        for (int i = gap;i < arr.length;i++){
            //j 下标前的元素比较
            int j = i - gap;
            int tem = arr[i];
            for (; j >= 0 ; j-= gap) {
                if(arr[j] > tem){
                    arr[j + gap] = arr[j];
                }else {
                    break;
                }
            }
            arr[j + gap] = tem;
        }
    }
    //法二
    public static void shellSort1(int[] arr){
        if(arr == null) return;
        if(arr.length == 1) return;

        //分组：可以选择/2或者/3分成小组
        int gap = arr.length;
        while(gap > 0){
            gap = gap / 2;
            int begin = 0;
            int count = gap;
            int end = arr.length - gap;
            while(count > 0){
             intsertSort1(arr,0,end);
             begin++;
             end++;
             count--;
            }
        }
    }
    private static void intsertSort1(int[] arr,int begin,int end){
        for (int i = begin + 1;i <= end; i++){
            int tem =arr[i];
            int j = i - 1;
            for (; j >=begin ; j--) {
                if(arr[j] > tem){
                    arr[j + 1] = arr[j];
                }else{
                    break;
                }
            }
            arr[j + 1] = tem;
        }
    }

    //堆排序：先创建大根堆，再进行排序
    public static void heapSort(int[] arr) {

        if (arr == null) return;
        if (arr.length == 1) return;

        //调用方法创建大根堆

        creatHeap(arr);

        //通过循环从后往前排序
        int usedSize = arr.length;
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr,0,i);
            usedSize--;
            siftDown(arr,0,usedSize);
        }
    }
private static void siftDown(int[] arr,int parent,int length){
        int child = parent * 2 + 1;
        while(child < length){
            if(child + 1 < length && arr[child] < arr[child + 1]){
                child++;
            }
            if(arr[parent] < arr[child]){
                swap(arr,parent,child);
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
}

    private static void creatHeap(int[] arr){
        //找到最下面的非叶子节点
        for (int parent = (arr.length - 2) >>1; parent >= 0 ; parent--) {
           siftDown(arr,parent,arr.length);
        }
    }
    private static void swap(int[] arr,int parent,int child){
        int tem = arr[parent];
        arr[parent] = arr[child];
        arr[child] = tem;
    }

    //选择排序
    public static void selectSort(int[] arr){
        if (arr == null) return;
        if (arr.length == 1) return;

        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j =  i + 1; j < arr.length; j++) {
                if(arr[minIndex] > arr[j]){
                    minIndex = j;
                }
            }
            swap(arr,i,minIndex);
        }

    }

    public int singleNumber(int[] nums) {
        //1.创建set
        HashSet<Integer> hashSet = new HashSet<Integer>();

        for(int i = 0; i < nums.length;i++){
            if(!hashSet.contains(nums[i])){
                hashSet.add(nums[i]);
            }else{
                hashSet.remove(nums[i]);
            }
        }
        for(int j = 0; j < nums.length;j++){
            if(hashSet.contains(nums[j])){
                return nums[j];
            }
        }
        return -1;

    }

    public static void main11(String[] args) {
//        HashSet<Integer> hashSet = new HashSet<>();
//        for (int i = 0; i < arr.length; i++) {
//            if(hashSet.isEmpty()){
//                hashSet.add(arr[i]);
//            }else if(hashSet.contains(arr[i - 1])){
//                hashSet.add(arr[i]);
//            }
//        }
//        return hashSet.remove(0);
     }

     //快速排序
    public static void  quickSort(int[] arr){
        int start = 0;
        int end = arr.length - 1;
        quick(arr,start,end);
    }
    private static void quick(int[] arr,int start,int end){

        if(start >= end) return;
        //快速排序的优化
        //1.当区间小于100时，选择插入排序
        if(end - start <= 100){
            shellSort(arr);
            return;
        }
        //2.三数取中法
        int ret = mid_three(arr,start,end);

        //获取下标
        int index = partition3(arr,start,end);
        swap(arr,index,start);

        //递归
        quick(arr,start,index -1);
        quick(arr,index + 1,end);

    }
    private static int mid_three(int[] arr,int start,int end){
        int mid = (start + end) / 2;

        if(arr[start] > arr[end]){
            if(arr[mid] > arr[start]){
                return start;
            }else if(arr[mid] < arr[end]){
                return end;
            }else{
                return mid;
            }
        }else{
            if(arr[mid] < arr[start]){
                return start;
            }else if(arr[mid] > arr[end]){
                return end;
            }else return mid;
        }
    }
    //挖坑法：从右边开始遍历，先将基准值位置填补，再从左边遍历，将右坑填补
    //左右下标相遇或者循环停止，将基准值放入终止的位置
    private static int partition1(int[] arr,int start,int end){
        //创建一个临时的变量
        int tem = arr[start];
        while(start < end){
            //遍历右边
            while(start < end && tem <= arr[end]){
                end--;
            }
            arr[start] = arr[end];
            //遍历左边
            while(start < end && tem >= arr[start]){
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = tem;
        return start;
    }
    //Hoare法：以第一个元素作为基准值，从右开始遍历，直到找到不大于基准值的元素，
    //然后从左开始遍历，直到找到不小于基准值的元素，将两个元素交换，直到循环终止，
    //将基准值与终止条件的下标交换
    private static int partition(int[] arr,int start,int end){
        //创建一个临时的变量
        int tem = arr[start];
        int i = start;
        int j = end;
        while(start < end){
            //遍历右边
            while(start < end && tem <= arr[end]){
                end--;
            }
            //遍历左边
            while(start < end && tem >= arr[start]){
                start++;
            }
           swap(arr,start,end);
        }
        //交换
        swap(arr,i,start);
        return start;
    }
    public static void shellSort2(int[] arr,int start,int end){
        if(arr == null) return;
        if(end == 1) return;

        int gap = end;
        while(gap > 0){
            gap = gap / 2;
            insertSort(arr,gap,start,end);
        }
    }
    public static void insertSort(int[] arr,int gap,int start,int end){

        for (int i = gap;i < end;i++){
            //j 下标前的元素比较
            int j = i - gap;
            int tem = arr[i];
            for (; j >= start ; j-= gap) {
                if(arr[j] > tem){
                    arr[j + gap] = arr[j];
                }else {
                    break;
                }
            }
            arr[j + gap] = tem;
        }
    }
    //快慢双指针：将第一个元素作为基准值，定义两个指针，初始值为prev = 0,cur = prev + 1
    //遍历数组，if快指针的值大于基准值，cur++，不大于基准值，并且prev+1位置的值不等于快指针
    //的值就进行交换，一直到循环终止，最后将基准值位置的与终止条件位置值交换。
    private static int partition3(int[] arr,int left,int right){
        int prev = left;
        int cur = prev + 1;
        //循环
       while(cur <= right){
            if(arr[cur] < arr[left] && arr[++prev] != arr[cur]){
                swap(arr,cur,prev);    //如果相等会将基准值覆盖，最后不能正确划分
            }
            cur++;
        }

        swap(arr,left,prev);
        return prev;
    }

    //非递归实现快排：申请一个栈，村数组范围
    public static void quickSortNonR(int arr[]){
        //1.创建栈并压栈
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        stack.push(arr.length -1);
        //2，循环
        while(!stack.isEmpty()){
            int right = stack.pop();
            int left = stack.pop();

            if(right - left <= 1)
                continue;

            int p = partition3(arr,left,right);

            stack.push(p + 1);
            stack.push(right);

            stack.push(left);
            stack.push(p - 1);

        }

    }

    //归并排序：先划分区域，再合并
    //时间复杂度：0(N * logN)
    //空间复杂度：0(logN + 范围）~O(N)
    public static  void mergeSort(int[] arr){
        merger(arr,0,arr.length -1);
    }

    private static void merger(int[] arr, int left, int right) {

        int mid = (left + right) / 2;
        //分割
        if(right - left < 1) return;

        //递归到至少两个元素
        merger(arr,left,mid);
        merger(arr,mid+1,right);

        //合并
        reback(arr,left,mid,right);
    }

    private static void reback(int[] arr,int left,int mid,int right) {

        int s1 = left;
        int e1 = mid;

        int s2 = mid + 1;
        int e2 = right;

        //创建临时数组
        int[] temArray = new int[right - left + 1];

        //循环遍历
        int k = 0;
        while(s1 <= e1 && s2 <= e2){

            if(arr[s1] < arr[s2]){
                temArray[k++] = arr[s1++];
            }else{
                temArray[k++] = arr[s2++];
            }
        }


        //不满足循环条件
        while(s1 <= e1){
            temArray[k++] = arr[s1++];
        }
        while(s2 <= e2){
            temArray[k++] = arr[s2++];
        }
        //拷贝回原来数组
        k = 0;
        for (int i = left; i <= right; i++) {
            arr[i] = temArray[k++];
        }

    }
    //非递归的归并排序：将元素局部排序，由开始的2个扩大到整个数组大小
    public static void mergeSortNonR(int[] arr){
        //每一组元素个数
        int gap = 1;
        while(gap < arr.length){
            for (int i = 0; i < arr.length; i = i + gap) {
                int left = i;

                int mid = left + gap -1;
                if(mid >= arr.length){
                    mid = arr.length -1;
                }
                int right = mid + gap;
                if(right >= arr.length){
                    right = arr.length -1;
                }

                //排序
                merger(arr,left,right);
                gap *= 2;
            }
        }
    }

    //计数排序：对于集中在某一区域的数据可以先创建一个数组统计每一个元素的个数，
    //再将每一个数据重新写入到原来数组中
    public static void countSort(int[] arr){
        if(arr == null || arr.length <= 1) return;

        //求最大值，求最小值
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(arr[i] > max){
                max = arr[i];
            }
            if(arr[i] < min){
                min = arr[i];
            }
        }
        int[] countArr = new int[max - min + 1];


        for (int i = 0; i < arr.length; i++) {
           countArr[arr[i] - min]++;
        }

        int k = 0;
        for (int i = 0; i < countArr.length; i++) {
            int size = countArr[i];

            while(size > 0){
                arr[k++] = i + min;
                size--;
            }
        }
    }

    //桶排序：获取数组中的最大值，求最大值是几位数，
    //创建一个二维数组作为桶，0 - 9下标为 -9 - (-1)
    //10 - 19下标为1 - 9，先得到个位数的余数，将数组值存放
    //二维数组桶中，遍历个位数取余数后，将桶的数据存放在数组中
    //重复以上过程，直到结束。

    public static void radixSort(int[] arr){
        if(arr == null || arr.length == 1) return;
        //获取最大值的长度
        int numMaxLen = getDigit(arr);
        //调用方法
        radixSort(arr,numMaxLen);
    }
    public static void radixSort(int[] arr,int numLen){
        int dev = 1;//除
        int mod = 10;//取模

        //循环次数
        for (int i = 0; i < numLen; i++) {
            //创建桶
            int[][] count = new int[20][];
            //第i次遍历数组
            for (int j = 0; j < arr.length; j++) {
                //获取下标位置
                int bucket = (arr[i] % mod) / dev + mod;
                //存放数值
                count[bucket] = appendArray(count[bucket],arr[j]);
            }
            //桶中元素存放在数组中
            int k = 0;
            for(int[] tem:count){
                for(int val : tem){
                    arr[k++] = val;
                }
            }
            //将取模 * 10，dev * 10
            mod *= 10;
            dev *= 10;
        }
    }
    private static int[] appendArray(int[] count,int val){
        int[] arr = Arrays.copyOf(count,count.length + 1);
        arr[arr.length - 1] = val;
        return arr;
    }

    private static int getDigit(int[] arr){
        int max = getMax(arr);
        return getLen(max);
    }

    private static int getLen(int max) {
        int len = 1;
        while(max > 9){
            max /= 10;
            len++;
        }
        return len;
    }

    private static int getMax(int[] arr){
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(max < arr[i]){
                max = arr[i];
            }
        }
        return max;
    }
    public static void main13(String[] args) {
        int[] arr = {231,33,61,3,552,29,9,7};
        countSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,3,4,1,5,7,0,6,0,1};
        countSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void main10(String[] args) {

        int[] arr = new int[5000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr.length - i;
        }
        long A5 = System.currentTimeMillis();
        //mergeSort(arr);
        //mergeSortNonR(arr);
        long B5 = System.currentTimeMillis();
        System.out.println("快速排序的运行时间：" + (B5 - A5));
    }
    public static void main9(String[] args) {
        int[] arr = {10,9,8,7,6,5,4,3,2,1};
        mergeSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

    }


    public static void main8(String[] args) {
                int[] arr = new int[5000];
                for (int i = 0; i < arr.length; i++) {
                    arr[i] = arr.length - i;
        }
        long A5 = System.currentTimeMillis();
        quickSort(arr);
        long B5 = System.currentTimeMillis();
        System.out.println("快速排序的运行时间：" +( B5 - A5));
    }
    public static void main7(String[] args) {
        int[] arr = {10,9,8,7,6,5,4,3,2,1};
        quickSortNonR(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

    }
    public static void main6(String[] args) {
        int[] arr = {10,9,8,7,6,5,4,3,2,1};
        selectSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }


    public static void main5(String[] args) {
        int[] arr = {10,9,8,7,6,5,4,3,2,1};
        shellSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    //打印程序运行的时间
    public static void main4(String[] args) {
        int[] arr = new int[5000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr.length - i;
        }
        int[] arr1 = Arrays.copyOf(arr,arr.length);
        int[] arr2 = Arrays.copyOf(arr,arr.length);
        int[] arr3 = Arrays.copyOf(arr,arr.length);
        int[] arr4 = Arrays.copyOf(arr,arr.length);
        int[] arr5 = Arrays.copyOf(arr,arr.length);

        long A1 = System.currentTimeMillis();
        insertSort(arr1);
        long B1 = System.currentTimeMillis();
        System.out.println("插入排序的运行时间：" +( B1 - A1));
        long A2 = System.currentTimeMillis();
        shellSort(arr2);
        long B2 = System.currentTimeMillis();
        System.out.println("希尔排序的运行时间：" +( B2 - A2));
        long A3 = System.currentTimeMillis();
        heapSort(arr3);
        long B3 = System.currentTimeMillis();
        System.out.println("堆排序的运行时间：" +( B3 - A3));
        long A4 = System.currentTimeMillis();
        selectSort(arr4);
        long B4 = System.currentTimeMillis();
        System.out.println("选择排序的运行时间：" +( B4 - A4));
        long A5 = System.currentTimeMillis();
        quickSort(arr5);
        long B5 = System.currentTimeMillis();
        System.out.println("快速排序的运行时间：" +( B5 - A5));
    }
    public static void main3(String[] args) {
        int[] arr = {10,9,8,7,6,5,4,3,2,1};
        heapSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void main2(String[] args) {
        int arr[] = {5,4,3,2,1,0};
        shellSort(arr);
    }
    public static void main1(String[] args) {
        int arr[] = {4,3,2,1};
        insertSort(arr);
    }
}